/**
 * @author LKQ
 * @date 2022/3/1 15:47
 * @description 深度优先遍历
 */
public class Solution {
    public static void main(String[] args) {

    }
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        dfs(head);
        return head;
    }
    public Node dfs(Node node) {
        //记住当前节点
        Node cur = node;
        // 记录链表的最后一个节点
        Node last = null;
        while (cur != null) {
            Node next = cur.next;
            // 如果有子节点，首先处理子节点
            if(cur.child != null) {
                Node childLast = dfs(cur.child);
                next = cur.next;

                // 将node与child相连
                cur.next = cur.child;
                cur.child.prev = cur;

                // 如果next 不为空，将last与next相连
                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }

                // 将child置空
                cur.child = null;
                last = childLast;
            }else {
                last = cur;
            }
            cur = next;
        }
        return last;
    }
}
